/*
 ============================================================================
 Name        : List.c
 Author      : lysong01@gmail.com
 Version     :
 Copyright   : email me if you use the code
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
//线性表的顺序存储结构
#define LIST_INIT_SIZE  100     //初始分配量
#define LISTINCREMENT   10      //分配增量
typedef int Elemtype;
typedef struct {
    Elemtype *data;			//data是数组首地址，data[i] <=> *(data+i)
    int length;             //当前长度
    int listsize;           //当前分配的容量
}Sqlist;

int initSqlist(Sqlist *L){
    L->data = (Elemtype *)malloc(LIST_INIT_SIZE*sizeof(Elemtype));
    if(!L->data) exit(-2);	//这里分配空间给Elemtype数组，而非给L，why？
    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
    return 1;
}

int insertSqlist(Sqlist *L, int i, Elemtype e){		//这里的i是指在第i个位置插入
    Elemtype *newbase;
	if(i<1 || i > L->length + 1) return 1;		//这里+1很重要，因为i是指第i个位置
    if(L->length >= L->listsize){
        newbase = (Elemtype *)realloc(L, (L->listsize + LISTINCREMENT)*sizeof(Elemtype));
        if(!newbase)	exit(EXIT_FAILURE);
        L->data = newbase;
        L->listsize = L->listsize + LISTINCREMENT;
    }
    int j;                  //c语言里貌似不能在for里直接定义int j
    for(j = L->length-1; j >= i-1; j--){		//i-1是顺序表中物理的插入位置
        L->data[j+1] = L->data[j];
    }
    L->data[i -1] = e;
    L->length++;
    //(*L).elem[i-1] = 2;	//事实证明这句话是起作用的，那就说只要形参是指针传递，那么其数据就一定改变
    return EXIT_SUCCESS;
}

int deleteSqlist(Sqlist *L, int i, Elemtype *e){
	if (i < 1 || i > L->length) {
		return EXIT_FAILURE;
	}
	e = L->data[i -1];
	int j;
	for (j = i-1; j <= (L->length -1); ++j) {	//要习惯统一for的使用，j指向的位置要是从插入位置到
		L->data[j] = L->data[j+1];				//表尾的元素，遍历表尾为了是表尾重新置空
	}
	L->length--;
	return EXIT_SUCCESS;
}

/*
 * 归并有序顺序线性表，核心：指针pc随着pa和pb的交错变化而一直变化
 */
void mergeSqlist(Sqlist La, Sqlist Lb, Sqlist *Lc){
	Elemtype *pa,*pb,*pc;
	pa = La.data; pb = Lb.data;
	Lc->listsize = Lc->length = La.length + Lb.length;
	pc = Lc->data = (Elemtype *)malloc(Lc->listsize*sizeof(Elemtype));
	if (!Lc->data) {
		exit(EXIT_SUCCESS);
	}
	while(pa <= La.data+La.length-1 && pb <= Lb.data+Lb.length-1){
		if (*pa <= *pb) {
			*pc++ = *pa++;
		} else {
			*pc++ = *pb++;
		}
	}
	while(pa <= La.data+La.length-1) *pc++ = *pa++;
	while(pb <= Lb.data+Lb.length-1) *pc++ = *pb++;
}
/*
int main(void) {
	printf("!!!Hello World,liyasong!!!\n");
	Sqlist La,Lb,Lc;			//定义一个数据结构变量
	initSqlist(&La);
	initSqlist(&Lb);
	int i;
	for(i = 0; i < 4; i++){
	   insertSqlist(&La, i+1, i);
	   insertSqlist(&Lb, i+1, i);
	}
	for(i = 0; i < La.length; i++){
	   printf("%d%d ", La.data[i],Lb.data[i]);
	}
	mergeSqlist(La, Lb, &Lc);
//	Elemtype e;
//	deleteSqlist(&L, 2, &e);
	printf("\n merge:");
	for(i = 0; i < Lc.length; i++){
		printf("%d ", Lc.data[i]);
	}
//	free(&L);			//why not make sense?
	return EXIT_SUCCESS;
}
*/
